// Filename: list.rs

/*
 * Copyright (c) 2020 Institute of Parallel And Distributed Systems (IPADS), Shanghai Jiao Tong University (SJTU)
 * OS-Lab-2020 (i.e., ChCore) is licensed under the Mulan PSL v1.
 * You can use this software according to the terms and conditions of the Mulan PSL v1.
 * You may obtain a copy of Mulan PSL v1 at:
 *   http://license.coscl.org.cn/MulanPSL
 *   THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR
 *   IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR
 *   PURPOSE.
 *   See the Mulan PSL v1 for more details.
 */

//  use std::cell::RefCell;
//  use std::rc::Rc;

#![no_std]

pub struct ListHead<T> {
    pub next: *mut ListHead<T>,
    pub prev: *mut ListHead<T>,
    pub data: T,
}

impl<T> ListHead<T> {
    pub fn new(data: T) -> Self {
        ListHead {
            next: core::ptr::null_mut(),
            prev: core::ptr::null_mut(),
            data,
        }
    }

    pub fn init(&mut self) {
        self.next = self;
        self.prev = self;
    }

    pub fn add(&mut self, new: *mut ListHead<T>) {
        unsafe {
            (*new).prev = self;
            (*new).next = self.next;
            (*(self.next)).prev = new;
            self.next = new;
        }
    }

    pub fn append(&mut self, new: *mut ListHead<T>) {
        let tail = self.prev;
        unsafe {
            (*tail).add(new);
        }
    }

    pub fn delete(&mut self) {
        unsafe {
            (*(self.prev)).next = self.next;
            (*(self.next)).prev = self.prev;
        }
    }

    pub fn is_empty(&self) -> bool {
        self.prev == self as *const _ as *mut _ && self.next == self as *const _ as *mut _
    }
}

#[macro_export]
macro_rules! container_of {
    ($ptr:expr, $type:ty, $field:ident) => {{
        (($ptr as *const _ as usize) - &(*(0 as *const $type)).$field as *const _ as usize)
            as *const $type
    }};
}

#[macro_export]
macro_rules! container_of_safe {
    ($ptr:expr, $type:ty, $field:ident) => {{
        let __ptr = $ptr;
        let __obj = container_of!(__ptr, $type, $field);
        if !__ptr.is_null() {
            Some(__obj)
        } else {
            None
        }
    }};
}

#[macro_export]
macro_rules! next_container_of_safe {
    ($obj:expr, $type:ty, $field:ident) => {{
        let obj = $obj;
        if let Some(obj) = obj {
            container_of_safe!(
                obj.borrow().$field.clone().as_ref().map(|x| &*x),
                $type,
                $field
            )
        } else {
            None
        }
    }};
}

#[macro_export]
macro_rules! list_entry {
    ($ptr:expr, $type:ty, $field:ident) => {{
        (($ptr as *const _ as usize) - &(*(0 as *const $type)).$field as *const _ as usize)
            as *mut $type
    }};
}

#[macro_export]
macro_rules! for_each_in_list {
    ($elem:ident, $type:ty, $field:ident, $head:expr) => {{
        let mut elem = container_of!($head.borrow().next.clone().unwrap().as_ref(), $type, $field);
        while &elem.$field != $head {
            elem = container_of!(elem.$field.next.clone().unwrap().as_ref(), $type, $field);
        }
    }};
}

#[macro_export]
macro_rules! __for_each_in_list_safe {
    ($elem:ident, $tmp:ident, $type:ty, $field:ident, $head:expr) => {{
        let mut elem = container_of!($head.borrow().next.clone().unwrap().as_ref(), $type, $field);
        let mut tmp = next_container_of_safe!(elem, $type, $field);
        while &elem.$field != $head {
            elem = tmp.unwrap();
            tmp = next_container_of_safe!(tmp, $type, $field);
        }
    }};
}

#[macro_export]
macro_rules! for_each_in_list_safe {
    ($elem:ident, $tmp:ident, $field:ident, $head:expr) => {{
        __for_each_in_list_safe!($elem, $tmp, $elem, $field, $head)
    }};
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_init() {
        let mut list = ListHead::new(42);
        list.init();

        assert!(list.is_empty());
    }

    #[test]
    fn test_add() {
        let mut list = ListHead::new(42);
        list.init();

        let mut node = ListHead::new(99);
        node.init();

        list.add(&mut node);

        assert!(!list.is_empty());
        assert!(!node.is_empty());
        assert_eq!(unsafe { &(*list.next) }.data, 99);
        assert_eq!(unsafe { &(*node.prev) }.data, 42);
    }

    #[test]
    fn test_append() {
        let mut list = ListHead::new(42);
        list.init();

        let mut node1 = ListHead::new(99);
        node1.init();

        let mut node2 = ListHead::new(88);
        node2.init();

        list.append(&mut node1);
        list.append(&mut node2);

        assert!(!list.is_empty());
        assert!(!node1.is_empty());
        assert!(!node2.is_empty());
        assert_eq!(unsafe { &(*list.next) }.data, 99);
        assert_eq!(unsafe { &(*node1.prev) }.data, 42);
        assert_eq!(unsafe { &(*node2.prev) }.data, 99);
    }

    #[test]
    fn test_delete() {
        let mut list = ListHead::new(42);
        list.init();

        let mut node = ListHead::new(99);
        node.init();

        list.add(&mut node);
        node.delete();

        assert!(list.is_empty());
    }
}

/*
#![no_std]

extern crate alloc;

use alloc::alloc::{alloc, dealloc, Layout};
use core::ptr;

pub struct ListHead<T> {
    next: Option<ptr::NonNull<ListHead<T>>>,
    prev: Option<ptr::NonNull<ListHead<T>>>,
    pub data: T,
}

impl<T> ListHead<T> {
    pub fn new(val: T) -> ptr::NonNull<Self> {
        let layout = Layout::new::<ListHead<T>>();
        let raw_ptr = unsafe { alloc(layout) as *mut ListHead<T> };
        if !raw_ptr.is_null() {
            unsafe {
                ptr::write(
                    raw_ptr,
                    ListHead {
                        next: None,
                        prev: None,
                        data: val,
                    },
                );
                (*raw_ptr).init();
            }
            ptr::NonNull::new(raw_ptr).unwrap()
        } else {
            panic!("Allocation failed");
        }
    }

    pub fn init(&mut self) {
        let tmp = self as *mut ListHead<T>;
        self.prev = Some(ptr::NonNull::new(tmp).unwrap());
        self.next = Some(ptr::NonNull::new(tmp).unwrap());
    }

    pub fn add(&mut self, new: ptr::NonNull<Self>) {
        unsafe {
            (*new.as_ptr()).next = self.next.take();
            (*new.as_ptr()).prev = Some(ptr::NonNull::new(self as *mut ListHead<T>).unwrap());
            if let Some(next) = (*new.as_ptr()).next {
                (*next.as_ptr()).prev = Some(new);
            }
            self.next = Some(new);
        }
    }

    pub fn next(&self) -> Option<*mut ListHead<T>> {
        if let Some(next) = self.next {
            Some(next.as_ptr())
        } else {
            None
        }
    }

    pub fn append(&mut self, new: ptr::NonNull<Self>) {
        unsafe {
            if let Some(mut tail) = self.next {
                (*tail.as_mut()).add(new);
            }
        }
    }

    pub fn delete(&mut self) {
        unsafe {
            if let Some(mut prev) = self.prev {
                (*prev.as_mut()).next = self.next;
                if let Some(mut next) = self.next {
                    (*next.as_mut()).prev = Some(prev);
                }
                self.prev = None;
                self.next = None;
                dealloc(
                    self as *mut ListHead<T> as *mut u8,
                    Layout::new::<ListHead<T>>(),
                );
            }
        }
    }

    pub fn is_empty(&self) -> bool {
        self.prev.is_none() && self.next.is_none()
    }
}

#[macro_export]
macro_rules! container_of {
    ($ptr:expr, $type:ty, $field:ident) => {{
        (($ptr as *const _ as usize) - &(*(0 as *const $type)).$field as *const _ as usize)
            as *const $type
    }};
}

#[macro_export]
macro_rules! container_of_safe {
    ($ptr:expr, $type:ty, $field:ident) => {{
        let __ptr = $ptr;
        let __obj = container_of!(__ptr, $type, $field);
        if !__ptr.is_null() {
            Some(__obj)
        } else {
            None
        }
    }};
}

#[macro_export]
macro_rules! next_container_of_safe {
    ($obj:expr, $type:ty, $field:ident) => {{
        let obj = $obj;
        if let Some(obj) = obj {
            container_of_safe!(
                obj.borrow().$field.clone().as_ref().map(|x| &*x),
                $type,
                $field
            )
        } else {
            None
        }
    }};
}

#[macro_export]
macro_rules! list_entry {
    ($ptr:expr, $type:ty, $field:ident) => {{
        (($ptr as *const _ as usize) - &(*(0 as *const $type)).$field as *const _ as usize)
            as *mut $type
    }};
}

#[macro_export]
macro_rules! for_each_in_list {
    ($elem:ident, $type:ty, $field:ident, $head:expr) => {{
        let mut elem = container_of!($head.borrow().next.clone().unwrap().as_ref(), $type, $field);
        while &elem.$field != $head {
            elem = container_of!(elem.$field.next.clone().unwrap().as_ref(), $type, $field);
        }
    }};
}

#[macro_export]
macro_rules! __for_each_in_list_safe {
    ($elem:ident, $tmp:ident, $type:ty, $field:ident, $head:expr) => {{
        let mut elem = container_of!($head.borrow().next.clone().unwrap().as_ref(), $type, $field);
        let mut tmp = next_container_of_safe!(elem, $type, $field);
        while &elem.$field != $head {
            elem = tmp.unwrap();
            tmp = next_container_of_safe!(tmp, $type, $field);
        }
    }};
}

#[macro_export]
macro_rules! for_each_in_list_safe {
    ($elem:ident, $tmp:ident, $field:ident, $head:expr) => {{
        __for_each_in_list_safe!($elem, $tmp, $elem, $field, $head)
    }};
}

#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn test_add() {
        let mut head: ptr::NonNull<ListHead<i32>> = ListHead::new(0);
        let new_node: ptr::NonNull<ListHead<i32>> = ListHead::new(1);

        unsafe {
            head.as_mut().init();
            head.as_mut().add(new_node);
            assert!(!head.as_ref().is_empty());
            assert_eq!(head.as_ref().next, Some(new_node));
            assert_eq!(new_node.as_ref().prev, Some(head));
        }
    }

    #[test]
    fn test_delete() {
        let mut head: ptr::NonNull<ListHead<i32>> = ListHead::new(0);
        let mut new_node: ptr::NonNull<ListHead<i32>> = ListHead::new(1);

        unsafe {
            head.as_mut().init();
            head.as_mut().add(new_node);
            new_node.as_mut().delete();
            assert!(!head.as_ref().is_empty());
            assert!(new_node.as_ref().is_empty());
        }
    }

    #[test]
    fn test_append() {
        let mut head: ptr::NonNull<ListHead<i32>> = ListHead::new(0);
        let mut new_node1: ptr::NonNull<ListHead<i32>> = ListHead::new(1);
        let mut new_node2: ptr::NonNull<ListHead<i32>> = ListHead::new(2);

        unsafe {
            head.as_mut().init();
            head.as_mut().append(new_node1);

            // 判断 append 成功
            assert_eq!(head.as_ref().next, Some(new_node1));
            assert_eq!(new_node1.as_ref().prev, Some(head));

            head.as_mut().append(new_node2);

            // 判断再次 append 成功
            assert_eq!(new_node1.as_ref().next, Some(new_node2));
            assert_eq!(new_node2.as_ref().prev, Some(new_node1));

            assert!(!head.as_ref().is_empty());
        }
    }
}
*/

/*
 use core::cell::RefCell;
 extern crate alloc;
 use alloc::rc::Rc;

 #[derive(Debug)]
 pub struct ListHead<T> {
     next: Option<Rc<RefCell<ListHead<T>>>>,
     prev: Option<Rc<RefCell<ListHead<T>>>>,
     pub data: T,
 }

 impl<T> ListHead<T> {
     pub fn new(val: T) -> Rc<RefCell<Self>> {
         Rc::new(RefCell::new(ListHead {
             next: None,
             prev: None,
             data: val,
         }.init()))
     }

     pub fn init(mut self) -> ListHead<T> {
         let tmp = Rc::new(RefCell::new(self));
         self.prev = Some(Rc::clone(&tmp));
         self.next = Some(Rc::clone(&tmp));
         self
     }

     pub fn add(&mut self, new: Rc<RefCell<ListHead<T>>>) {
         new.borrow_mut().next = self.next.take();
         new.borrow_mut().prev = Some(Rc::clone(
             &self.next.clone().unwrap().borrow().prev.clone().unwrap(),
         ));
         if let Some(next) = new.borrow_mut().next {
             next.borrow_mut().prev = Some(Rc::clone(&new))
         }
         self.next = Some(Rc::clone(&new))
     }

     pub fn append(&mut self, new: Rc<RefCell<ListHead<T>>>) {
         if let Some(tail) = self.prev.clone() {
             //tail.borrow_mut().next = Some(Rc::new(RefCell::new(new)))
             tail.borrow_mut().add(new)
         }
     }

     pub fn delete(&mut self) {
         if let Some(prev) = self.prev {
             let mut prev_borrowed = prev.borrow_mut();
             prev_borrowed.next = self.next; // update prev -> next
             if let Some(next) = self.next {
                 next.borrow_mut().prev = self.prev; // update next -> prev
             }
         }
         self.prev = None;
         self.next = None;
     }

     pub fn is_empty(&self) -> bool {
         self.prev.is_none() && self.next.is_none()
     }
 }



 #[macro_export]
 macro_rules! container_of {
    ($ptr:expr, $type:ty, $field:ident) => {{
        (($ptr as *const _ as usize) - &(*(0 as *const $type)).$field as *const _ as usize) as *const $type
    }};
}

#[macro_export]
macro_rules! container_of_safe {
    ($ptr:expr, $type:ty, $field:ident) => {{
        let __ptr = $ptr;
        let __obj = container_of!(__ptr, $type, $field);
        if !__ptr.is_null() {
            Some(__obj)
        } else {
            None
        }
    }};
}

 #[macro_export]
 macro_rules! next_container_of_safe {
    ($obj:expr, $type:ty, $field:ident) => {{
        let obj = $obj;
        if let Some(obj) = obj {
            container_of_safe!(obj.borrow().$field.clone().as_ref().map(|x| &*x), $type, $field)
        } else {
            None
        }
    }};
}

#[macro_export]
macro_rules! list_entry {
    ($ptr:expr, $type:ty, $field:ident) => {{
        container_of!($ptr, $type, $field)
    }};
}

#[macro_export]
macro_rules! for_each_in_list {
    ($elem:ident, $type:ty, $field:ident, $head:expr) => {{
        let mut elem = container_of!($head.borrow().next.clone().unwrap().as_ref(), $type, $field);
        while &elem.$field != $head {
            elem = container_of!(elem.$field.next.clone().unwrap().as_ref(), $type, $field);
        }
    }};
}

#[macro_export]
macro_rules! __for_each_in_list_safe {
    ($elem:ident, $tmp:ident, $type:ty, $field:ident, $head:expr) => {{
        let mut elem = container_of!($head.borrow().next.clone().unwrap().as_ref(), $type, $field);
        let mut tmp = next_container_of_safe!(elem, $type, $field);
        while &elem.$field != $head {
            elem = tmp.unwrap();
            tmp = next_container_of_safe!(tmp, $type, $field);
        }
    }};
}

#[macro_export]
macro_rules! for_each_in_list_safe {
    ($elem:ident, $tmp:ident, $field:ident, $head:expr) => {{
        __for_each_in_list_safe!($elem, $tmp, $elem, $field, $head)
    }};
}


 /*
 trait ContainerOf<T> {
     fn container_of(ptr: Rc<RefCell<Self>>) -> Rc<RefCell<Self>>;
 }

 impl<T> ContainerOf<T> for ListHead<T> {
     fn container_of(ptr: Rc<RefCell<Self>>) -> Rc<RefCell<Self>> {
         ptr
     }
 }

 #[macro_export]
 macro_rules! list_entry {
     ($ptr:expr, $type:ty, $field:ident) => {
         Self::container_of(&$ptr)
     };
 }

 #[macro_export]
 macro_rules! for_each_in_list {
     ($elem:ident, $type:ty, $field:ident, $head:expr) => {
         let mut $elem = Self::container_of(&$head.next.unwrap());
         while &$elem.$field != &$head {
             $elem = Self::container_of(&$elem.$field.next.unwrap());
         }
     };
 }

 #[macro_export]
 macro_rules! for_each_in_list_safe {
     ($elem:ident, $tmp:ident, $type:ty, $field:ident, $head:expr) => {
         let mut $elem = Self::container_of(&$head.next.unwrap());
         let mut $tmp = next_container_of_safe!($elem, $type, $field);
         while &$elem.$field != &$head {
             $elem = $tmp;
             $tmp = next_container_of_safe!($elem, $type, $field);
         }
     };
 }*/

 /*
 fn main() {
     let head: Rc<RefCell<ListHead<i32>>> = ListHead::new(0);
     let new_node: Rc<RefCell<ListHead<i32>>> = ListHead::new(1);

     head.borrow_mut().init();
     head.borrow_mut().add(new_node);
 }

 #[cfg(test)]
 mod tests {
     use super::*;
/*
     #[test]
     fn test_init() {
         let head: Rc<RefCell<ListHead<i32>>> = ListHead::new(0);
         head.borrow_mut().init();
         assert!(head.borrow().is_empty());
     }
*/
     #[test]
     fn test_add() {
         let head: Rc<RefCell<ListHead<i32>>> = ListHead::new(0);
         let new_node1: Rc<RefCell<ListHead<i32>>> = ListHead::new(1);

         head.borrow_mut().init();
         head.borrow_mut().add(Rc::clone(&new_node1));

         assert!(!head.borrow().is_empty());
         assert!(new_node1.borrow().prev.is_some());
     }

     #[test]
     fn test_delete() {
         let head: Rc<RefCell<ListHead<i32>>> = ListHead::new(0);
         let new_node1: Rc<RefCell<ListHead<i32>>> = ListHead::new(1);

         head.borrow_mut().init();
         head.borrow_mut().add(Rc::clone(&new_node1));

         new_node1.borrow_mut().delete();

         println!("After delete - head: {:?}", head.clone());
         println!("After delete - new_node1: {:?}", new_node1.clone());

         assert!(!head.borrow().is_empty());
         assert!(new_node1.borrow().is_empty());
     }

     #[test]
     fn test_append() {
         let head: Rc<RefCell<ListHead<i32>>> = ListHead::new(0);
         let new_node1: Rc<RefCell<ListHead<i32>>> = ListHead::new(1);
         let new_node2: Rc<RefCell<ListHead<i32>>> = ListHead::new(1);

         head.borrow_mut().init();
         head.borrow_mut().add(Rc::clone(&new_node1));
         head.borrow_mut().append(Rc::clone(&new_node2));

         println!("After append - head: {:?}", head.clone());
         println!("After append - new_node2: {:?}", new_node2.clone());

         assert!(!head.borrow().is_empty());
         assert!(new_node2.borrow().prev.is_some());
     }
 }
*/
*/
